package com.day1_栈和队列;

import java.util.LinkedList;

/**
 * 题目：剑指 Offer 09. 用两个栈实现队列
 * 题目内容：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
 * 思路：
 * 用一个辅助栈实现，将元素栈中的元素出栈到辅助栈中，再出辅助栈中出栈，就可以实现队列
 * 出栈时需要分三种情况，见下面deleteHead（）函数
 * 用时：1h2m
 * 日期：20220814
 */
class CQueue{
    LinkedList<Integer> A,B;//B作为辅助栈，存放A的倒序数据
    //    //用LinkedList构造两个栈
    public CQueue() {
        A=new LinkedList<Integer>();
        B=new LinkedList<Integer>();
    }
    //添加元素
    public void appendTail(int value) {
        A.addLast(value);
    }
    //删除元素
    public int deleteHead() {
        //情况1：B中有A的倒序元素，直接出栈就可以
        if(!B.isEmpty()){
            return B.removeLast();//删除B集合的最后元素，其实就是删除栈顶元素
        }
        //情况2：A中为空，这个时候A,B都为空，直接返回-1
        if(A.isEmpty())return -1;
        //情况3：B中没有元素，A也不为空，这个时候先将A中的元素出栈到B中
        while(!A.isEmpty()){
            B.addLast(A.removeLast());
        }
        return B.removeLast();
    }
}
public class 剑指offer09_用两个栈实现队列 {
    public static void main(String[] args) {
        CQueue obj=new CQueue();
        obj.appendTail(1);
        obj.appendTail(2);
        obj.appendTail(3);
        int param_1 = obj.deleteHead();
        int param_2 = obj.deleteHead();
        int param_3 = obj.deleteHead();
        System.out.println(param_1);
        System.out.println(param_2);
        System.out.println(param_3);
    }
}
